package com.lance.answer;

import com.alibaba.fastjson.JSON;

public class Test1 {


//    public static void getNextVal(String T,int[] nextVal){
//        int i=1,j=0;
//        nextVal[1]=0;
//        while (i<T.length()-1){
//            if(j==0||T.toCharArray()[i]==T.toCharArray()[j]){
//                ++i;
//                ++j;
//                if(T.toCharArray()[i]==T.toCharArray()[j]){
//                    nextVal[i]=j;
//                }else {
//                    nextVal[i]=nextVal[j];
//                }
//            }else {
//                j=nextVal[j];
//            }
//        }
//    }

    public static void getNextVal(String T,int[] nextVal){
        int i=1,j=0;
        nextVal[0]=0;
        while (i<T.length()-1){
            if(j==0||T.toCharArray()[i]==T.toCharArray()[j]){
                ++i;
                ++j;
                if(T.toCharArray()[i]==T.toCharArray()[j]){
                    nextVal[i]=j;
                }else {
                    nextVal[i]=nextVal[j];
                }
            }else {
                j=nextVal[j];
            }
        }
    }

    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();

        int[] next = new int[p.length];

        next[0] = -1;

        int j = 0;

        int k = -1;

        while (j < p.length - 1) {

            if (k == -1 || p[j] == p[k]) {

                if (p[++j] == p[++k]) { // 当两个字符相等时要跳过

                    next[j] = next[k];

                } else {

                    next[j] = k;

                }

            } else {

                k = next[k];

            }

        }

        return next;

    }


    public static void main(String[] args) {
        String T="ababaaababaa";
        int[] nextVal =new int[20];
        getNextVal(T,nextVal);

        System.err.println(JSON.toJSONString(nextVal));
        System.err.println(JSON.toJSONString(getNext(T)));
    }
}
